/*
	Copyright (c) 2008, Grant Jones <grant@podtronics.com>.
	All rights reserved.

	Redistribution and use in source and binary forms, with or
	without modification, are permitted provided that the following
	conditions are met:

		Redistributions of source code must retain the above copyright
		notice, this list of conditions and the following disclaimer.
		
		Redistributions in binary form must reproduce the above copyright
		notice, this list of conditions and the following disclaimer in
		the documentation and/or other materials provided with the
		distribution.
		
		Neither the name of the gxjones.com nor the names of its
		contributors may be used to endorse or promote products derived
		from this software without specific prior written permission.
	
	THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
	LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
	FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
	COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
	INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
	(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
	SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
	STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
	ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
	OF THE POSSIBILITY OF SUCH DAMAGE.
	
	http://www.opensource.org/licenses/bsd-license.php
*/

/*
 *  edb_domain_select.c
 *  scatterd
 *
 *  Created by Grant Jones on 3/5/08.
 *
 */

#include "edb_main.h"
#include "edb_msg_parser.h"
#include "edb_msg_utils.h"
#include "edb_msg_expr.h"
#include "strmap.h"
#include "edb_domain.h"
#include "edb_domain_select.h"
#include "edb_domain_index.h"
#include "cmap_sort.h"

typedef struct
{
	int bAscending;
	int err_count;
	AttrValue *orderby;
} select_sort_ctx_t;

static int select_compare( void *ctx, const void *a, const void *b )
{
	select_sort_ctx_t *sort_ctx = (select_sort_ctx_t *)ctx;
	AttrList *a_attrs;
	AttrList *b_attrs;
	if( sort_ctx->bAscending )
		a_attrs = (AttrList *)a, b_attrs = (AttrList *)b;
	else
		a_attrs = (AttrList *)b, b_attrs = (AttrList *)a;
	
	AttrValue *a_orderby_val = strmap_lookup(a_attrs, (const char *)sort_ctx->orderby->key.z, sort_ctx->orderby->key.n);
	AttrValue *b_orderby_val = strmap_lookup(b_attrs, (const char *)sort_ctx->orderby->key.z, sort_ctx->orderby->key.n);
		
	if(!a_orderby_val || !b_orderby_val )
	{
		/* one or both of the items for comparison is missing the required attribute */
		sort_ctx->err_count ++;
		return 0;
	}
	
//	if( edb_numeric_value( &left_value, &left_num_value ) && edb_numeric_value( &right_value, &right_num_value ) )
//		return (da==db?0:(da<db?-1:1));
	const void *p1 = a_orderby_val->value.z;
	const void *p2 = b_orderby_val->value.z;
	int n1 = a_orderby_val->value.n;
	int n2 = b_orderby_val->value.n;
	int c;
	c = memcmp(p1, p2, n1<n2 ? n1 : n2);
	if( c==0 )
		c = n1 - n2;
	return c;
}

void edb_domain_select_sort( cmapStruct *result_items, AttrValue *orderby )
{
	select_sort_ctx_t ctx;
	ctx.err_count = 0;
	ctx.bAscending = 1;
	ctx.orderby = orderby;

	if( orderby->value.n > 0 && strncasecmp( (const char *)orderby->value.z, "DESC", orderby->value.n ) == 0 )
		ctx.bAscending = 0;

	cmap_sortbyvalue( result_items, &ctx, select_compare );
//	printf("err count: %d\n", ctx.err_count );
}

int exprIsAttrKey( Expr *expr, const char *attr_name, size_t attr_name_sz )
{
	return (	expr->op == TK_ID &&
				expr->token.n == attr_name_sz &&
				memcmp( expr->token.z, attr_name, attr_name_sz ) == 0 );
}
#define exprIsAbsolute( e ) ( e->op == TK_STRING || e->op == TK_INTEGER || e->op == TK_FLOAT || e->op == TK_VARIABLE )

int edb_domain_select_opt1( Expr *where_expr, cmapStruct *base_search_keys )
{
	/* _name = <something specific> */
	
	if( !where_expr )
		return 0;
	
	if( where_expr->op != TK_EQ )	/* this optimization is really pretty specific */
		return 0;
	if( exprIsAttrKey( where_expr->pLeft, "_name", 5 ) && exprIsAbsolute( where_expr->pRight ) )
	{	
		rtvalue_t *key_ptr = mempool_malloc_named(base_search_keys->mempool, sizeof(rtvalue_t), "select name key" );
		key_ptr->data = (void *)where_expr->pRight->token.z;
		key_ptr->size = where_expr->pRight->token.n;

		/* note: strmap_assign will make a 2nd copy of the token, this isn't really avoidable without some extra fancy work */
		strmap_assign(base_search_keys, key_ptr->data, key_ptr->size, key_ptr);
		return 1;
	}
	else if( exprIsAttrKey( where_expr->pRight, "_name", 5 ) && exprIsAbsolute( where_expr->pLeft ) )
	{	
		rtvalue_t *key_ptr = mempool_malloc_named(base_search_keys->mempool, sizeof(rtvalue_t), "select name key" );
		key_ptr->data = (void *)where_expr->pLeft->token.z;
		key_ptr->size = where_expr->pLeft->token.n;

		strmap_assign(base_search_keys, key_ptr->data, key_ptr->size, key_ptr);
		return 1;
	}
	return 0;
}

int edb_domain_select_opt2(
				edb_domain_ref_t *dref,
				Expr *where_expr,
				cmapStruct *base_search_keys )
{
	void *index_ptr;
	
	Token *index_name = NULL;
	Token *key = NULL;
	if( !where_expr )
		return 0;
	if( where_expr->op != TK_EQ )
		return 0;
	
	/* <attribute name> = <somethign specific> */
	
	/* do we have a index for the attribute? */
		
	if( where_expr->pLeft->op == TK_ID &&
		exprIsAbsolute( where_expr->pRight ) &&
		(index_ptr = strmap_lookup(&dref->d->index, (const char *)where_expr->pLeft->token.z, where_expr->pLeft->token.n)) )
	{
		index_name = &where_expr->pLeft->token;
		key = &where_expr->pRight->token;
	}
	else if( where_expr->pRight->op == TK_ID &&
		exprIsAbsolute( where_expr->pLeft ) &&
		(index_ptr = strmap_lookup(&dref->d->index, (const char *)where_expr->pRight->token.z, where_expr->pRight->token.n)) )
	{	
		index_name = &where_expr->pRight->token;
		key = &where_expr->pLeft->token;
	}
	
	if( !index_name || !key )
	{
/*		printf("edb_domain_select_opt2 not used: no index or key\n");*/
		return 0;
	}
	
	rtree_t *rt = dref->d->rt_db_ptr;
	off_t last_loc;
	rtvalue_t index_name_val;
	rtvalue_t attr_val;
	TagManagerEnumStruct tmes;
	TagStruct *tag;
	off_t tag_loc;
	
	index_name_val.data = (void *)index_name->z;
	index_name_val.size = index_name->n;
	attr_val.data = (void *)key->z;
	attr_val.size = key->n;
	
	last_loc = edb_domain_loc_index( dref->d, &index_name_val, &attr_val );
	if(last_loc == 0ULL)
	{
		/* this is success, just an empty set */
		return 1;
	}
	
/*	printf("Using opt2 on select [last_loc: %d]\n", (int)last_loc);*/
	

	/* note we use the tag-level enumeration, not the
	** higher-level radix-tree enumeration */
	
	if( tagm_beginEnumTags( rt->tms, &tmes, last_loc ) )
		return -1;

	while( (tag = tagm_nextTag( rt->tms, &tmes, &tag_loc )) )
	{
		if( !(tag->hdr.bFlags & TAG_OVERFLOW) )
			continue;
/*
		printf("name from index: \"");
		fwrite(tag->data, tag->hdr.dlen, 1, stdout);
		printf("\"\n");
*/		
		rtvalue_t *key_ptr = mempool_malloc_named(base_search_keys->mempool, sizeof(rtvalue_t), "select name key" );
		str_entry_t *se = strmap_assign(base_search_keys, (const char *)tag->data, tag->hdr.dlen, key_ptr);		
		if(!se ) continue;
		key_ptr->size = tag->hdr.dlen;
		key_ptr->data = se->key;	/* slight hack to avoid duplicate data allocation */
	}
	tagm_endEnumTags(rt->tms, &tmes);			

	/* yup, we used the index */
	return 1;
}

int edb_domain_select_opt3(
				edb_domain_ref_t *dref,
				Expr *where_expr,
				cmapStruct *base_search_keys )
{
	int beval = 0;
	strmapEnumStruct e;
	rtvalue_t *search_key_ptr;
	char *key;
	size_t key_sz;
	
	if( !where_expr || !(where_expr->op == TK_AND || where_expr->op == TK_OR ) )
		return 0;
		
	/* <expr1> AND/OR <expr2>, where expr1 and expr2 can be evaluated by edb_domain_select_opt2 or edb_domain_select_opt3 */
	strmapStruct *search_keys1 = cmap_new(base_search_keys->mempool);
	strmapStruct *search_keys2 = cmap_new(base_search_keys->mempool);
	
	
	beval = (edb_domain_select_opt1( where_expr->pLeft, search_keys1 ) || edb_domain_select_opt2( dref, where_expr->pLeft, search_keys1 ) || edb_domain_select_opt3( dref, where_expr->pLeft, search_keys1 ) ) &&
			(edb_domain_select_opt1( where_expr->pRight, search_keys2 ) || edb_domain_select_opt2( dref, where_expr->pRight, search_keys2 ) || edb_domain_select_opt3( dref, where_expr->pRight, search_keys2 ) );
	if( !beval )
		return 0;
	
	if( where_expr->op == TK_AND )
	{
		/* intersection */
		strmap_enum(search_keys1, &e);
		while( (search_key_ptr = strmap_enum_next(&e, &key, &key_sz)) )
		{
			if( !strmap_lookup(search_keys2, key, key_sz) )
				continue;
			strmap_assign(base_search_keys, key, key_sz, search_key_ptr);
		}
	}
	else
	{
		/* union */
		strmap_enum(search_keys1, &e);
		while( (search_key_ptr = strmap_enum_next(&e, &key, &key_sz)) )
			strmap_assign(base_search_keys, key, key_sz, search_key_ptr);
			
		strmap_enum(search_keys2, &e);
		while( (search_key_ptr = strmap_enum_next(&e, &key, &key_sz)) )
			strmap_assign(base_search_keys, key, key_sz, search_key_ptr);
	}
	
	return 1;	
}

void edb_domain_select_base(
				edb_domain_ref_t *dref,
				AttrList *selattrlist,
				Expr *where_expr,
				void *groupby_arg,
				void *having_arg,
				AttrList *orderby_arg,
				AttrList *limit_arg, 
				cmapStruct *result_items )
{
	rtenum_t rte;
	strmapStruct *base_search_keys = cmap_new(result_items->mempool);
	rtvalue_t found_key, found_data;
	strmapEnumStruct key_e;
	char *key_idx;
	size_t key_idx_sz;
	rtvalue_t *search_key;

	
	/* if where_expr can be reduced to search for a specific _name
	** key, then we do so */
	int using_opt1 = edb_domain_select_opt1( where_expr, base_search_keys );
	/* if where_expr can use index, then use it: */
	int using_opt2 = edb_domain_select_opt2( dref, where_expr, base_search_keys );
	/* if where_expr uses AND/OR then try to do opt1 or opt2 on the expr: */
	int using_opt3 = edb_domain_select_opt3( dref, where_expr, base_search_keys );

	edb_log_printf(0,"opt1: %d opt2: %d opt3: %d\n", using_opt1, using_opt2, using_opt3 );

	/* use the root _name index: */
	rtree_use( dref->d->rt_db_ptr, NULL, 0 );			/* position list cursor at root */	
	rtree_use( dref->d->rt_db_ptr, dref->d->dname, dref->d->dname_sz );
	rtree_use( dref->d->rt_db_ptr, EDB_NAME_KEY, strlen(EDB_NAME_KEY) );
	
	
	/* add the _name wildcard if the previous calls didn't add anything: */
	if( base_search_keys->num <= 0ULL )
	{
		rtvalue_t wildcard_key = { 0, NULL };
		if( (using_opt1 || using_opt2 || using_opt3) )
			return;
	
//		strmap_assign(base_search_keys, "*", 1, &wildcard_key);
		
		edb_log_printf(0,"slow wildcard query\n");
		
		/* gather all name keys (this is not an efficient operation, memory or cpu wise) */
		rt_enum_all_begin( dref->d->rt_db_ptr, &rte, NULL );

		while( rt_enumerate_nextkey( &rte, &found_key ) == 0 )
		{
			rtvalue_t *key_ptr = mempool_malloc_named(base_search_keys->mempool, sizeof(rtvalue_t), "select name key" );
			str_entry_t *se = strmap_assign(base_search_keys, (const char *)found_key.data, found_key.size, key_ptr);		
			if(!se ) continue;
			key_ptr->size = found_key.size;
			key_ptr->data = se->key;	/* slight hack to avoid duplicate data allocation */
		}

		/* needs to be moved to radixtree_enum: */
		cmap_destroy(rte.key_stack);	
		
		
	}

	
	int limit_num = -1;
	int offset_num = -1;

	/* LIMIT */
	if( limit_arg )
	{
		double dlimit_num, doffset_num;
		AttrValue *limit = strmap_lookup(limit_arg, "limit", 5);
		AttrValue *offset = strmap_lookup(limit_arg, "offset", 6);
//		edb_log_printf(0, "limit value: ");
//		edb_log_dump(0, limit->value.z, limit->value.n );
//		edb_log_printf(0, "\n");
		
		if( limit && edb_numeric_value( &limit->value, &dlimit_num ) )
			limit_num = (dlimit_num+0.5);
		if( offset && edb_numeric_value( &offset->value, &doffset_num ) )
			offset_num = (doffset_num+0.5);
	}
	
//	edb_log_printf(0, "select limits: %d; offset: %d\n", limit_num, offset_num );


	
	/* TODO: enumeration should only pull out attributes from items specified by selattrlist,
	** right now all attributes will be pull into memory and processed */
	
	
	strmap_enum(base_search_keys, &key_e);

	while( (search_key = strmap_enum_next(&key_e, &key_idx, &key_idx_sz)) )
	{
		AttrList *attrs_out = NULL;
		
		if( rt_get(dref->d->rt_db_ptr, search_key, &found_data) )
		{
			/* error or not found */
			continue;
		}
		
		/* destruct will create an AttrList out of the raw data returned by 
		** the enumerate operation, it makes a copy of the data allocating
		** new memory */
		edb_domain_destruct_item( result_items->mempool, dref, &found_data, &attrs_out );
		
		if( where_expr && !edb_domain_eval(where_expr,attrs_out) )
			continue;
		
		cmap_assign(result_items, cmap_gethighestkey(result_items)+1, attrs_out);		
	}
	
	/* ORDER BY SORT */
	
	/* TODO: orderby_arg must become a real list, not a strmap which is unordered */
	if( orderby_arg )
	{
		strmapEnumStruct orderby_e;	
		char *key;
		size_t key_sz;
		AttrValue *orderby_attr;
		strmap_enum(orderby_arg, &orderby_e);
		orderby_attr = strmap_enum_next(&orderby_e, &key, &key_sz);
		if( orderby_attr )
			edb_domain_select_sort( result_items, orderby_attr );
	}
	
	/* enforce limits */
	if( limit_num >= 0 )
	{
		/* TODO: the cmap should be able to do this trivially, since num is
		** not really a public value */
		/* TODO: enforce offset -- the cmap will handle this */
		if( result_items->num > limit_num )
			result_items->num = limit_num;
	}
	


}


void edb_domain_select(	edb_domain_ref_t *dref,
				AttrList *selattrlist,
				Expr *where_expr,
				void *groupby_arg,
				void *having_arg,
				AttrList *orderby_arg,
				AttrList *limit_arg, 
				cmapStruct *result_items )
{
	cmapStruct *attrlist_items = cmap_new( result_items->mempool );
	AttrList *attrs_out;
	CMAP_KEY_TYPE item_num;
	cmapEnumStruct attr_items_e;

	strmapEnumStruct e;	
	char *key;
	size_t key_sz;
	AttrValue *attr_val;
	AttrValue *sel_attr_val;
	int cnt = 0;
	
	/* _base does the work of gathering all the items */
	edb_domain_select_base( dref, selattrlist, where_expr, groupby_arg, having_arg, orderby_arg, limit_arg, attrlist_items );

	/* post-process items converting them into the net format */

	cmap_enum(attrlist_items, &attr_items_e);

	while( (attrs_out = cmap_enum_next(&attr_items_e, &item_num)) )
	{
		/* allocate for maximum number of attributes */
		edb_net_item_t *ri = edb_add_result( result_items, attrs_out->num );			
		
		/* no selattrlist means we need to select all attributes */
		if( !selattrlist )
		{
			/* convert attribute to net attribute */
			strmap_enum(attrs_out, &e);
			cnt = 0;
			while( (attr_val = strmap_enum_next(&e, &key, &key_sz)) )
			{
				/* allocate off the less temporary result items pool */
				edb_malloc_result_attr( result_items->mempool,  &ri->attrs[cnt], (const char *)attr_val->key.z, attr_val->key.n, attr_val->value.n );
				memcpy( ri->attrs[cnt].value, attr_val->value.z, attr_val->value.n );
				
				cnt++;
				
				assert( cnt <= ri->attr_count );	/* might happen if collisions occur due to the fact we use attrs_out->num which doesn't take into account the chaining */
			}

			ri->attr_count = cnt;
		}
		else
		{
			/* use only the specified attributes */
			strmap_enum(selattrlist, &e);
			cnt = 0;
			while( (sel_attr_val = strmap_enum_next(&e, &key, &key_sz)) )
			{
				attr_val = strmap_lookup(attrs_out, (const char *)sel_attr_val->key.z, sel_attr_val->key.n);
				if(!attr_val)
				{
					/* item doesn't have requested attribute */
					continue;
				}
				/* allocate off the less temporary result items pool */
				edb_malloc_result_attr( result_items->mempool,  &ri->attrs[cnt], (const char *)attr_val->key.z, attr_val->key.n, attr_val->value.n );
				memcpy( ri->attrs[cnt].value, attr_val->value.z, attr_val->value.n );
				
				cnt++;
				
				assert( cnt <= ri->attr_count );	/* might happen if collisions occur due to the fact we use attrs_out->num which doesn't take into account the chaining */
			}			
			
			ri->attr_count = cnt;
			
		}
		
		if( ri->attr_count == 0 )
		{
			/* remove empty result sets */
			cmap_remove(result_items, cmap_gethighestkey(result_items) );
		}
	}
	

}






